#include <cstddef>
#include <iostream>
using namespace std;
enum Colour {
    RED,
    BLACK
};
template <class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;

    pair<K, V> _kv;

    int _col;

    RBTreeNode(const pair<K, V>& kv) 
        :_left(nullptr),
        _right(nullptr),
        _parent(nullptr),
        _kv(kv),
        _col(RED) {}
};

template <class K, class V>
class RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    bool insert(const pair<K, V>& kv) {
        if(_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
        }
        return true;
        Node* parent = nullptr;
        Node* cur = _root;
        // 查看有没有这个值
        while(cur) {
            if(cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            }else if(cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            }else {
                return false;
            }
        }
        cur = new Node(kv);
        if(parent->_kv.first < kv.first) {
            parent->_right = cur;
        }else {
            parent->_left = cur;
        }
        cur->_parent = parent;
        // 我们要处理的是父亲是红色的
        while(parent && parent->_col == RED) {
            Node* grandfather = parent->_parent;
            if(parent == grandfather->_left) {
                // 这个情况
                //  g
                //p   u
                Node* uncle = grandfather->_right;
                // 有uncle且为红色，变颜色继续处理
                if(uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 继续处理上面
                    cur = grandfather;
                    parent = cur->_parent;
                }else { // uncle为黑色，旋转变颜色
                    if(cur == parent->_left) {
                        //    g
                        //  p   u
                        //c
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }else {
                        //     g
                        // p     u
                        //   c
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }else { // 在右边
                Node* uncle = grandfather->_left;
                // 有叔叔且是红色
                if(uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                }else { // 不存在叔叔，或者是为黑色
                    //    g
                    // u     p
                    //          c
                    if(cur == parent->_right) {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK; // 这里可能被情况1变成了黑色
        return true;
    }
    void RotateR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if(subLR) {
            subLR->_parent = parent;
        }
        Node* pParent = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        if(parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        }else {
            if(pParent->_left == parent) {
                pParent->_left = subL;
            }else {
                pParent->_right = subL;
            }
            subL->_parent = pParent;
        }
    }
    void RotateL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        if(subRL) {
            subRL->_parent = parent;
        }
        Node* pParent = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;
        if(pParent == nullptr) {
            _root = subR;
            subR->_parent = nullptr;
        }else {
            if(parent == pParent->_left) {
                pParent->_left = subR;
            }else {
                pParent->_right = subR;
            }
            subR->_parent = pParent;
        }
    }
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }
    bool IsBalance() {
        if(_root == nullptr) {
            return true;
        }
        if(_root->_col == RED) {
            return false;
        }
        // 我们首先要拿到一个参考的值
        int refNum = 0;
        Node* cur = _root;
        while(cur) {
            if(cur->_col == BLACK) {
                ++refNum;
            }
            cur = cur->_left;
        }
        return Check(_root, 0, refNum);
    }
    Node* Find(const K& key) {
    Node* cur = _root;
    while(cur) {
        if(cur->_kv.first < key) {
            cur = cur->_left;
        }else if(cur->_kv.first > key) {
            cur = cur->_right;
        }else {
            return cur;
        }
    }
    return nullptr;
    }


private:
    bool Check(Node* root, int num, const int refNUm) {
        if(root == nullptr) {
            if(num != refNUm) {
                cout << "存在黑色节点的数量不相等的路径" << endl;
                return false;
            }
            return true;
        }

        if(root->_col == RED && root->_parent->_col == RED) {
            cout << root->_kv.first << "存在连续的红色节点" << endl;
            return false;
        }
        if(root->_col == BLACK) {
            num++;
        }
        return Check(root->_left, num, refNUm) && Check(root->_right, num, refNUm);
    }
    // 为了更加的简单我们这里使用递归写
    void _InOrder(Node* root) {
        if(root == nullptr) {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }
    Node* _root = nullptr;
};






